An image, particularly a multi-valued image includes many pieces of information, and requires a huge memory size for storage and much time for transmission. For this reason, upon storing or transmitting an image, high-efficiency encoding is used to reduce a data size of the image by processing for removing redundancy of the image or changing the contents of the image to a level at which deterioration of image quality is visually unrecognizable.
For example, JPEG, which is recommended by ISO and ITU-T as an international standard encoding method of a still image, computes discrete cosine transforms (DCTs) for respective blocks (8×8 pixels) of image data, thus obtaining DCT transform coefficients. JPEG compresses the image data by quantizing the DCT transform coefficients and entropy-encoding the quantized transform coefficients. As a compression technique using this DCT, H261, MPEG-1/2/4, and the like are known in addition to JPEG.
As partial processing of this DCT transform or processing for transforming image data, a Hadamard transform is known. The Hadamard transform is an orthogonal transform that uses a transform matrix including elements of only 1 or −1, i.e., a simplest orthogonal transform implemented by only additions and subtractions.
A transform matrix H2 of a 2-point Hadamard transform is defined by:
                              H          2                =                              1                          2                                ⁡                      [                                                            1                                                  1                                                                              1                                                                      -                    1                                                                        ]                                              (        1        )            
A general N (=2n)-point Hadamard transform matrix HN can be recursively defined by a Kronecker product between an (N/2)-point Hadamard transform matrix HN/2 and the 2-point Hadamard transform matrix H2:
                                                                        H                N                            =                                                H                                      N                    /                    2                                                  ⊗                                  H                  2                                                                                                        =                                                1                                      2                                                  ⁡                                  [                                                                                                              H                                                      N                            /                            2                                                                                                                                                H                                                      N                            /                            2                                                                                                                                                                                        H                                                      N                            /                            2                                                                                                                                                -                                                      H                                                          N                              /                              2                                                                                                                                                            ]                                                                                        (        2        )            
For example, from the above definition, a 4-point Hadamard transform matrix is expressed by:
                              H          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                                                1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                      ]                                              (        3        )            
This transform matrix is called a natural type, and basis vectors are not arranged in a sequency-order. By repeating permutations of basis vectors, the basis vectors in the second row are moved to the fourth row, and those in the original third and fourth rows are moved to rows upper by one row. Then, a transform matrix WH4 in which the order of the basis vectors is a sequency-order is generated:
                              WH          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                        ]                                              (        4        )            
The above transform matrix is called a Walsh type or Walsh-Hadamard transform matrix. The Hadamard transform is known as a lossless orthogonal transform. Both the natural type and Walsh type allow lossless transforms, and their transform matrices are symmetric matrices.
Another symmetric matrix obtained by permuting the basis vectors of the natural type Hadamard transform matrix H4 is available in addition to the Walsh type. That symmetric matrix is a transform matrix T4 which includes diagonal components of +1 as features and is given by:
                              T          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                    1                                                                      -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                      ]                                              (        5        )            
The present invention will explain examples using the Hadamard transform of this type.
Generally speaking, a Hadamard transform is a reversible transform, as described above. However, this merely means a mathematically reversible transform. That is, the reversible transform is premised on that no calculation errors are generated during transform and inverse transform processes, and fixed- or floating-point calculations are required as a data format for this purpose. Also, all significant digit numbers need to be held after the transform processing.
However, in a Hadamard transform used in transform encoding, particularly lossless transform encoding, the significant digit numbers are to be reduced as much as possible after the transform processing. More specifically, since fractional part data generated by transforming integer input data is considered as a digit number (information) apparently increased from the input data, this fractional part data is to be removed. However, when this fractional part data is simply rounded, reversibility is lost. For example, when four data:
123, 78, 84, 56
undergo Hadamard transform processing using the transform matrix given by equation (5), the transform results are:
170.5, 30.5, 36.5, 8.5
When these values are converted into integers by simply rounding up their fractional parts, we have:
171, 31, 37, 9
It should be noted that the transform matrix given by equation (5) is a transposed matrix. That is, transforming the integer-converted results using equation (5) again is equivalent to inverse transforming, and their inverse transform results are:
124, 78, 84, 56
Upon examining these results, first data “123” becomes “124” via the transform and inverse transform processes. That is, this means that a Hadamard transform that outputs integer-converted data cannot guarantee losslessibility.
In the following description, a Hadamard transform that outputs integer-converted data will be referred to as an integer type Hadamard transform, and an integer type Hadamard transform that allows a reversible transform will be referred to as an integer type lossless-Hadamard transform or lossless-Hadamard transform.
Related arts that implement a lossless 4-point-Hadamard transform can be roughly classified into two techniques. One technique uses a Ladder Network (ladder calculations). The other technique executes round processing of a certain rule after a linear Hadamard transform. The former is disclosed in [Shinji Fukuma, Koichi Oyama, Masahiro Iwahashi, and Noriyoshi Kanbayashi, “Lossless 8-point fast discrete cosine transform using lossless Hadamard transform”, IEICE technical report, IE99-65, pp. 37-44, October 1999] (to be referred to as reference 1 hereinafter).
The latter is disclosed in Japanese Patent Laid-Open No. 2003-258645 (to be referred to as reference 2 hereinafter).
In reference 1, the lossless transform is implemented by a complicated sequence of decomposing a 4-point Hadamard transform matrix into triangular matrices, and substituting the triangular matrices by ladder calculations. FIG. 9 shows an example of the arrangement of reference 1. As shown in FIG. 9, the circuit arrangement is complicated, and it is hard to intuitively recognize the contents of calculations. For this reason, mistakes upon software or hardware implementation are hard to be found out, and the calculation processing volume is not so small.
On the other hand, a method disclosed in reference 2 as the latter technique rounds up fractional parts of an odd number of data for transform coefficients of fractional part data obtained by the linear Hadamard transform, and truncates fractional parts of another odd number of data. This reference 2 is characterized by only the method of round processing, but it does not devise to reduce calculations of the linear Hadamard transform and to reduce a processing volume required for the round processing.